# -*- coding:utf-8 -*-
from collections import Counter
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        if len(numbers) <= 0:
            return 0
        d = Counter(numbers)
        middle = len(numbers)>>1
        for i,v in d.items():
            if v>middle:
                return i
        return 0

    def MoreThanHalfNum_Solution2(self, numbers):
        # write code here
        t = 1
        d = numbers[0]
        for i in numbers[1:]:
            if t == 0:
                d = i
                t += 1
                continue
            elif i == d:
                t += 1
            else:
                t -= 1
        middle = len(numbers) >> 1
        z = 0
        for i in numbers:
            if i == d:
                z += 1
        if z > middle:
            return d
        return 0


S = Solution()
# print(S.MoreThanHalfNum_Solution([1, 2, 3, 2, 2, 2, 5, 4, 2]))
# print(S.MoreThanHalfNum_Solution([1, 2, 3, 3, 3, 3, 4]))
# print(S.MoreThanHalfNum_Solution([1, 2]))

print(S.MoreThanHalfNum_Solution2([4,2,4,1,4,2]))

